﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using UnityEngine;

namespace ns
{
    public class StringQuestion : MonoBehaviour
    {

        //7.整数反转
        //https://leetcode-cn.com/problems/reverse-integer/solution/
        //方法：弹出和推入数字 & 溢出前进行检查 ，通过数学的方法
        public int Reverse(int x)
        {
            long rev = x % 10;   //获取最后一位
            while (x / 10 < 0 || x / 10 > 0)  //整除 256 / 10 = 25 
            {
                x = x / 10; //去掉最后一位
                rev = rev * 10 + x % 10; //推入数字
            }
            if (rev > int.MaxValue || rev < int.MinValue) //判断溢出
            {
                return 0;
            }
            else return (int)rev;
        }

        //8. 字符串转换整数 (atoi)
        //https://leetcode-cn.com/problems/string-to-integer-atoi/
        //正则表达式(空间是和时间是性能最低的~)
        public int MyAtoi(string str)
        {
            // ^ :必须从字符串的开头开始匹配    [+-]：匹配集合单个字符+-  ? :匹配上一个元素零次或一次(+ -)。  \d+ ：任何十进制数字匹配(+ : 上一个元素一次或多次)
            str = System.Text.RegularExpressions.Regex.Match(str.Trim(), @"^[+-]?\d+").ToString(); //
            //使用正则表达式，在指定的输入字符串中搜索指定的正则表达式的第一个匹配项。Trim从当前字符串的开头和结尾删除所有空白字符后剩余的字符串
            int o_Num;
            bool t_IsParse = int.TryParse(str, out o_Num); //是否包含要转换的数字的字符串。
            if (t_IsParse)
            {
                return o_Num;
            }
            else
            {
                if (string.IsNullOrEmpty(str))
                {
                    return 0;
                }
                else //溢出的情形
                {
                    if (str[0] == '-')
                    {
                        return -2147483648;
                    }
                    else
                    {
                        return 2147483647;
                    }
                }
            }
        }

        //14. 最长公共前缀
        //https://leetcode-cn.com/problems/longest-common-prefix/
        //纵向扫描
        //思路：对每个字符串第一列开始进行扫描，知道有一列不相同，如果第一列就不相同，就没有最长公共前缀.
        //两个for循环，第一个for控制字符串第几个开始比较，第二个for控制第几行字符串开始比较
        public string LongestCommonPrefix(string[] strs)
        {
            if (strs == null || strs.Length == 0)
            {
                return "";
            }
            int length = strs[0].Length;
            int count = strs.Length;
            for (int i = 0; i < length; i++) //字符串个数的循环
            {
                char c = strs[0][i]; //获取到第一行第i个字符
                for (int j = 1; j < count; j++) // 第几行字符串,从第二行开始
                {
                    if (i == strs[j].Length || strs[j][i] != c)
                    {
                        return strs[0].Substring(0, i); //i是指长度
                    }
                }
            }
            return strs[0];
        }







        //public enum AtoiState
        //{
        //    Start,
        //    Find,
        //    End,
        //}

        //8. 字符串转换整数 (atoi)
        //https://leetcode-cn.com/problems/string-to-integer-atoi/
        //高性能解法
        //public int MyAtoi(string s)
        //{
        //    var chars = s.Trim().ToCharArray();
        //    if (chars.Length <= 0) return 0;

        //    var boundary = Int32.MaxValue / 10;
        //    int start = 1, sign = 1;
        //    int ans = 0;

        //    if (chars[0] == '-') sign = -1;
        //    else if (chars[0] != '+') start = 0;

        //    for (var i = start; i < chars.Length; i++)
        //    {
        //        if (chars[i] < '0' || chars[i] > '9') break;
        //        if (ans > boundary || ans == boundary && chars[i] > '7')
        //        {
        //            return sign == 1 ? Int32.MaxValue : Int32.MinValue;
        //        }
        //        ans = ans * 10 + chars[i] - '0';
        //    }
        //    return ans * sign;
        //}



        //20.有效括号
        //https://leetcode-cn.com/problems/valid-parentheses/
        //
        //
        public bool IsValid(string s)
        {
            return false;
        }

        //28. 实现 strStr()
        //https://leetcode-cn.com/problems/implement-strstr/
        //暴力法 两个for循环
        public int StrStr(string haystack, string needle)
        {
            if (haystack == needle || string.IsNullOrEmpty(needle)) return 0; //完全相等或者空字符串
            var result = -1;
            var length = haystack.Length;
            var needleLength = needle.Length;
            var needleStart = needle[0]; //数值

            for (var i = 0; i <= length - needleLength; i++) //i的范围0 - 俩字符串的差值
            {
                if (haystack[i] != needleStart) //先找到第一个相同的字符，在匹配剩下字符
                {
                    continue;
                }
                var matched = 1; //匹配数+1
                for (var j = i + 1; j < i + needleLength; j++) //第一个字符匹配，匹配剩下的字符
                {
                    if (haystack[j] == needle[j - i])
                    {
                        matched++; //匹配+1
                    }
                    else
                    {
                        break; //不匹配跳出
                    }
                }
                if (matched == needleLength) { result = i; break; }
            }
            return result;
        }

        //38、外观数列
        //https://leetcode-cn.com/problems/count-and-say/
        //纯打表..... 双层for循环
        //解题思路：第一个for循环存储数据：需要描述的字符n-1，第二个for循环,获取到描述后的字符，区分字符串的边界，从第二个字符串开始比较，先描述前一个，在描述后一个
        public string CountAndSay(int n)
        {
            System.Text.StringBuilder curr = new StringBuilder("1"); //最终结果
            StringBuilder prev;
            int count; //子字符串的数量
            char say;
            for (int i = 1; i < n; i++)
            {
                prev = curr;
                curr = new StringBuilder();
                count = 1;
                say = prev[0]; //【描述】第一个字符串

                for (int j = 1; j < prev.Length; j++)  //从第二个字符串开始判断
                {
                    if (prev[j] != say) //和后面不相等，先描述出来，在描述下一个字符串
                    {
                        curr.Append(count).Append(say); //添加新的子字符串
                        count = 1;
                        say = prev[j]; // 描述下一个字符串
                    }
                    else count++;
                }
                curr.Append(count).Append(say); //添加新的子字符串
            }
            return curr.ToString();
        }



        //125. 验证回文串
        //https://leetcode-cn.com/problems/valid-palindrome/
        //回文串是正字符和反字符是一模一样的，去掉数字和空白
        //左右指针，向中心移动


        public bool IsPalindrome(string s)
        {
            if (s == null)
            {
                return false;
            }
            int left = 0;
            int right = s.Length - 1;
            while (left < right) //左右指针
            {
                while (left < right && !char.IsLetterOrDigit(s[left])) //是否属于字母或十进制数字类别。
                {
                    left++; //不遇到字母才会+1
                }
                while (left < right && !char.IsLetterOrDigit(s[right]))
                {
                    right--;
                }
                if (char.ToLower(s[left]) != char.ToLower(s[right]))
                {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

        //242 有效的字母异位词（字符出现的种类相同次数相同）
        //https://leetcode-cn.com/problems/valid-anagram/
        //哈希表，参考桶排序,也可以使用字典
        public bool IsAnagram(string s, string t)
        {
            if (s.Length != t.Length) return false;
            int[] table = new int[26]; //创建26只桶
            for (int i = 0; i < s.Length; i++)
            {
                table[s[i] - 'a']++; //unicode字符
                table[t[i] - 'a']--;
            }
            foreach (var item in table)
            {
                if (item != 0)
                {
                    return false;
                }
            }
            return true;

        }



        //344 反转字符串
        //https://leetcode-cn.com/problems/reverse-string/
        //双指针
        public void ReverseString(char[] s)
        {
            int n = s.Length;
            for (int left = 0, right = n - 1; left < right; left++, right--)
            {
                var temp = s[right];
                s[right] = s[left];
                s[left] = temp;
            }
        }

        //387 字符串中的第一个唯一字符
        //https://leetcode-cn.com/problems/first-unique-character-in-a-string/
        //字典键值对
        public int FirstUniqChar(string s)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < s.Length; i++) //第一次遍历存储
            {
                if (dic.ContainsKey(s[i])) //字典存在
                    dic[s[i]]++;
                else
                    dic.Add(s[i], 1);
            }
            for (int i = 0; i < s.Length; i++) //第二次检查
            {
                if (dic[s[i]] == 1)
                    return i;
            }
            return -1;
        }


        //剑指 Offer 40. 最小的k个数
        //https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
        //思路1：直接sort（面试容易pass）
        //思路2：大根堆，堆大顶（root值总是大于或等于左右叶子节点），数组的前半段元素都为根节点，其余元素为叶子节点 !!!!!!很重要
        //思路3：选择排序
        public int[] GetLeastNumbers(int[] arr, int k)
        {
            BuildMaxHeap(arr); //创建大顶堆,完成arr交换
            for (int i = arr.Length - 1; i >= 0; i--)
            {
                Swap(arr, 0, i); //堆顶元素与无序区最后一位交换（使堆顶元素进入有序区）
                MaxHeapify(arr, 0, i); //重新将无序区调整为大顶堆
            }
            int[] result = new int[k];
            for (int i = 0; i < k; i++)
            {
                result[i] = arr[i];
            }
            return result;
        }

        private void BuildMaxHeap(int[] arr)
        {
            for (int i = arr.Length / 2 - 1; i >= 0; i--) //根据大顶堆的性质，前半段元素为root节点，后半段元素都是叶子节点
            {
                MaxHeapify(arr, i, arr.Length); //调整大顶堆，从最底层的最后一个root节点开始
            }
        }

        private void MaxHeapify(int[] arr, int curIdx, int heapLength)
        {
            int left = 2 * curIdx + 1;//左叶子的位置  这是对应关系 0  1  2  ， 1 3 4， 2 5 6 ，3 7 8
            int right = 2 * curIdx + 2;//左叶子的位置
            int MaxIdx = curIdx;        //记录此根节点、左右节点

            if (left < heapLength && arr[left] > arr[MaxIdx]) //更节点与左节点比较
            {
                MaxIdx = left;
            }
            if (right < heapLength && arr[right] > arr[MaxIdx]) //更节点与右节点比较
            {
                MaxIdx = right;
            }
            if (curIdx != MaxIdx) //左右节点有大于更节点的情况
            {
                Swap(arr, MaxIdx, curIdx); //交换数值
                MaxHeapify(arr, MaxIdx, heapLength);//继续递归调整，确认更节点左右节点符合规则
            }
        }

        private void Swap(int[] arr, int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }




        //字段
        public char[] num344;
        public int num7;
        public string s387;
        public string str1242;
        public string str2242;
        public string str125;
        public string str8;



        /// <summary>
        /// 图形界面操作
        /// </summary>
        private void OnGUI()
        {
            if (GUI.Button(new Rect(30, 30, 120, 30), "344反转字符串"))
            {
                ReverseString(num344);
                foreach (var item in num344)
                {
                    Debug.Log(item);
                    Debug.Log(256 / 10);
                }

            }

            if (GUI.Button(new Rect(30, 80, 120, 30), "7整数反转"))
            {
                Debug.Log(num7);
                var result = Reverse(num7);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 130, 120, 30), "387字符串第一个唯一字符"))
            {
                Debug.Log(s387);
                var result = FirstUniqChar(s387);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 180, 120, 30), "242有效的字母异位词"))
            {
                var result = IsAnagram(str1242, str2242);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 230, 120, 30), "125验证回文串"))
            {
                var result = IsPalindrome(str125);
                Debug.Log(result);
            }

            if (GUI.Button(new Rect(30, 280, 120, 30), "8字符串转换整数"))
            {
                var result = MyAtoi(str8);
                Debug.Log(result);
            }

        }
    }
}